//  Implementazione della struttura dati heap binario attraverso
//  l'uso di array dinamico.
//  Heap.c
//  TecnicheDiProgrammazione
//

#include <stdio.h>
#include "Heap.h"
#include "TArray.h"
#include <assert.h>
#include <stdlib.h>

#define INIT_LENGHT 100
#define left(J)(2*(J)+1)
#define right(J)(2*(J)+2)
#define parent(J)(((J)-1)/2)


//private methods
void max_heapify(THeap *h, int j);
void max_heapify_reverse(THeap *h, int j);
int heap_search(THeap *h, int key);

//Definizione della stuttura dell'heap
struct SHeap{
    TArray *arr;
};

/*
 Consente di creare un nuovo heap.
 @return il puntatore al nuovo heap creato.
 */
THeap* heap_create(){
    THeap *heap = (THeap*)malloc(sizeof(THeap));
    assert(heap!=NULL);
    heap->arr = array_create(INIT_LENGHT);
    return heap;
}

/*
 Dealloca le risorse associate all'heap.
 @param h puntatore all'heap da deallocare.
 */
void heap_destroy(THeap *h){
    array_destroy(h->arr);
    free(h);
    h = NULL;
}

/*
 Consente di ripristinare al condizione di massimalità di un heap
 a partire da un heap massimale in tutti i suoi nodi tranne che in
 quello di posizione j.
 Il criterio utilizzato si basa sulla verifica della proprietà secondo la
 quale h[j] è maggiore di ogni suo discendente.
 @param h Heap da ripristinare
 @param j Indice dell'elemento che viola le proprietà dell'heap
 */
void max_heapify(THeap *h, int j){
    int k = j;
    //Verifico se j ha figli e qual'è il maggiore
    int size = array_length(h->arr);
    if( right(j) < size && array_get(h->arr, right(j))->key > array_get(h->arr, k)->key)
        k = right(j);
    if( left(j) < size && array_get(h->arr, left(j))->key > array_get(h->arr, k)->key)
        k = left(j);
    
    //Se uno dei figli è maggiore del padre allora scambio il padre
    // con il figlio maggiore
    if(k!=j){
        array_swap(h->arr, j, k);
        max_heapify(h, k);
    }
}

/*
 Consente di ripristinare al condizione di massimalità di un heap
 a partire da un heap massimale in tutti i suoi nodi tranne che in
 quello di posizione j.
 Il criterio utilizzato si basa sulla verifica della proprietà secondo la
 quale h[j] è minore di ogni suo ascendente.
 @param h Heap da ripristinare
 @param j Indice dell'elemento che viola le proprietà dell'heap
 */
void max_heapify_reverse(THeap *h, int j){
    //sposto l'elemento verso l'alto se maggiore del padre
    while (j>0 && array_get(h->arr, parent(j))->key < array_get(h->arr, j)->key) {
        array_swap(h->arr, parent(j), j);
        j = parent(j);
    }
}

/*
 Consente di costruire un heap binario massimale a partire da un vettore di TInfo
 @param info vettore di TInfo
 @param size dimensiozne del vettore di TInfo
 @return l'heap binario massimale
 */
THeap* build_max_heap(TInfo info[], int size){
    //Costruisco a partire dal vettore statico un vettore dinamico
    TArray *array = array_create(size);
    int i;
    for(i = 0; i<size; i++){
        array_insert(array, i, info[i]);
    }
    //Costruisco l'heap
    THeap *heap = (THeap*)malloc(sizeof(THeap));
    heap->arr = array;
    
    //Alla k-esima iterazione, con 1<=k<=array.lenght/2, tutti gli heap che hanno come radice
    // un nodo con indice compreso tra k+1 e array.lenght/2 sono massimali.
    for(i = (array_length(array))/2; i>=0; i--)
        max_heapify(heap, i);
    
    return heap;
}

/*
 Consente di inserire un nuovo elemento nello heap.
 @param h heap in cui inserire l'elemento
 @param info elemento da inserire
 */
void heap_insert(THeap *h, TInfo info){
    //Inserisco l'elemento in ultima posizione
    array_insert(h->arr, array_length(h->arr), info);
    //Ripristino la proprietà di massimalità
    max_heapify_reverse(h, array_length(h->arr)-1);
}

/*
 Consente di cancellare da un heap l'elemento indentificato dalla chiave key
 @param h Heap contenente l'elemento da cancellare
 @param key Chiave che identifica l'elemento da cancellare
 */
void heap_delete(THeap *h, int key){
    //Trovo l'indice dell'elemento da eliminare
    int i = heap_search(h, key);
    //Elimino l'elemento
    heap_delete_at_index(h, i);
    
}

/*
 Permette la cancellazione dell'elemento di indice i dall'heap
 @param h Heap in cui si trova l'elemento da cancellare
 @param i Indice dell'elemento da cancellare
 */
void heap_delete_at_index(THeap *h, int i){
    int arr_lenght = array_length(h->arr);
    
    if(i<array_length(h->arr)){
        //Scambio l'elemento da cancellare con l'ultimo elemento dell'heap
        array_swap(h->arr, i, arr_lenght-1);
        //Cancello ultimo elemento
        array_remove(h->arr, arr_lenght-1);
        //Ripristino la proprietà di massimalità
        max_heapify(h, i);
    }
        
}

/*
 Restituisce un puntatore all'elemento dell'heap con chiave key
 @param h Heap da cui leggere l'elemento
 @param key chiave associata all'elemento
 @return puntatore all'elemento di chiave key
 */
TInfo* heap_get(THeap *h, int key){
    //Trovo l'indice dell'elemento
    int i = heap_search(h, key);
    //Prelevo l'elemento
    return heap_get_at_index(h, i);
}

/*
 Consente di prelevare l'elemento in posizione i-esima dell'heap
 @param h Heap da cui leggere l'elemento
 @param i indice dell'elemento da prelevare
 @return puntatore all'elemento di indice i
*/
TInfo* heap_get_at_index(THeap *h, int i){
    if(i>=array_length(h->arr))
        return NULL;
    else
        return array_get(h->arr, i);
        
}

/*
 Consente di ricercare l'indice corrispondende al nodo di chiave key
 @param h Heap in cui cercare
 @param key chiave dell'elemento da cercare
 @return indice dell'elemento trovato. -1 in caso di ricerca fallita.
 */
int heap_search(THeap *h, int key){
    int arr_lenght = array_length(h->arr);
    int i = 0;
    while(i<arr_lenght && array_get(h->arr, i)->key != key)
        i++;
    
    if(i<arr_lenght){
        return i;
    }
    else
        return -1;

}

/*
 Consente di ordinare un vettore di TInfo sfruttando gli heap binari.
 Complessita computazionale O(NlogN)
 @param v il vettore da ordinare
 @param size il riempimento del vettore
 */
void heap_sort(TInfo v[], int size){
    //Costruiamo l'heap a partire dall'arraydi info
    THeap* heap = build_max_heap(v, size);
    int i;
    
    //Alla k-esima iterazione, con 1<=k<=array_lenght-1, v[i+1..array_lenght-1]
    // sarà ordinato mentre heap rappresenterà l'heap massimale associato alla
    // parte del vettore non ancora ordinata. La radice dell'heap conterrà l'elemento
    // da inserire alla prossima iterazione in v[i].
    for(i = array_length(heap->arr)-1; i>=1; i--){
        v[i] = *heap_get_at_index(heap, 0);
        heap_delete_at_index(heap, 0);
        //La delete esegue anche la max_heapify
    }
}

/*
 Consente di variare la chiave associata ad un elemento di un heap e di 
 ripristinare la massimalità dell'heap stesso.
 Utilizzata principalemente nelle code di priorità.
 @param h Heap da modificare
 @param i Indice in cui si trova l'elemento
 @param newKey nuova chiave da sostituire nell'elemento
 */
void heap_set_key(THeap *h, int i, int newKey){
    TInfo *info = heap_get_at_index(h, i);
    if(info!=NULL){
        //Si vuole decrementare la chiave
        if(info->key > newKey){
            info->key = newKey;
            max_heapify(h, i);
        }
        //Si vuole incrementare la chiave
        else{
            info->key = newKey;
            max_heapify_reverse(h, i);
        }
    }
}










